#include "main/utils.h"
using namespace std;

vector<vector<int>> updateMatrix(const vector<vector<int>>& M) {
  int row = M.size();
  int col = M[0].size();
  vector<vector<int>> D;
  D.resize(row);
  for (int i = 0; i < row; ++i) {
    D[i].resize(col, 0);
  }

  deque<vector<int>> deque;
  for (int i = 0; i < row; ++i) {
    for (int j = 0; j < col; ++j) {
      if (M[i][j] == 0) {
        deque.push_back({i, j});
      } else {
        D[i][j] = INT_MAX;
      }
    }
  }

  vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  while (!deque.empty()) {
    auto cur = deque.front();
    deque.pop_front();
    int cur_dist = D[cur[0]][cur[1]];
    for (auto dir : dirs) {
      int r = cur[0] + dir[0];
      int c = cur[1] + dir[1];
      if (r >= 0 && r < row &&
          c >= 0 && c < col) {
        if (D[r][c] > cur_dist + 1) {
          D[r][c] = cur_dist + 1;
          deque.push_back({r, c});
        }
      }
    }
  }
  return D;
}

int main() {
  vector<vector<int>> M = {{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};
  auto D = updateMatrix(M);
  printVec("o107", D);

  return 0;
}
